{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        def helper(start, end):\n",
    "            if(start > end):\n",
    "                return [[]]\n",
    "            result = []\n",
    "            for i in range(start, end+1):\n",
    "                left_nodes = helper(start, i-1)\n",
    "                right_nodes = helper(i+1, end)\n",
    "                for l in left_nodes:\n",
    "                    for r in right_nodes:\n",
    "                        root = TreeNode(i)\n",
    "                        root.left = l\n",
    "                        root.right = r\n",
    "                        result.append(root)\n",
    "            return result\n",
    "        if(n == 0):\n",
    "            return []\n",
    "        return helper(1,n)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateTrees(self, n):\n",
    "    def helper(tree):\n",
    "        # tree 为有序数组\n",
    "        ans = []\n",
    "        # 遍历可能的根结点\n",
    "        for i, val in enumerate(tree):\n",
    "            # left、right 分别为左右子树包含的结点\n",
    "            left, right = tree[:i], tree[i+1:]\n",
    "            # 若左子树为 NULL，则令其为 [None]\n",
    "            for ltree in helper(left) or [None]:\n",
    "                # 若右子树为 NULL，则令其为 [None]\n",
    "                for rtree in helper(right) or [None]:\n",
    "                    root = TreeNode(val)\n",
    "                    root.left, root.right = ltree, rtree\n",
    "                    ans.append(root)\n",
    "        return ans\n",
    "    return helper(range(1, n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "思路如下：\n",
    "\n",
    "对于连续整数序列[left, right]中的一点i，若要生成以i为根节点的BST，则有如下规律：\n",
    "\n",
    "i左边的序列可以作为左子树结点，且左儿子可能有多个，所以有vector<TreeNode *> left_nodes = generate(left, i - 1);；\n",
    "i右边的序列可以作为右子树结点，同上所以有vector<TreeNode *> right_nodes = generate(i + 1, right);；\n",
    "产生的以当前i为根结点的BST（子）树有left_nodes.size() * right_nodes.size()个，遍历每种情况，即可生成以i为根节点的BST序列；\n",
    "然后以for循环使得[left, right]中每个结点都能生成子树序列。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "a = Solution()\n",
    "res = a.generateTrees(3)\n",
    "#print(res)\n",
    "for ls in res:\n",
    "    print(ls.val )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Input: 3\n",
    "Output:\n",
    "[\n",
    "  [1,null,3,2],\n",
    "  [3,2,null,1],\n",
    "  [3,1,null,null,2],\n",
    "  [2,1,3],\n",
    "  [1,null,2,null,3]\n",
    "]\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
